#include <iostream>
#include <algorithm>
using namespace std;

#include "Chapter9.h"
#include "array.h"

CArrayFor_9_3_6::CArrayFor_9_3_6(int size):CArray(size)
{

}

CArrayFor_9_3_6::CArrayFor_9_3_6(const int *initData, const int len)
	:CArray(initData, len)
{
}

CArrayFor_9_3_6::CArrayFor_9_3_6(const CArrayFor_9_3_6 & origin)
	:CArray(origin.data, origin.remainDataCount())
{
//	start = origin.start;
//	end = origin.end;
//	memncpy(data, origin.data, sizeof(origin.data));
}

CArrayFor_9_3_6 CArrayFor_9_3_6::getPart(int start, int end)const 
{
	return CArrayFor_9_3_6(data+start, end - start + 1);
}

#if 0
int t, length_A;
void Print(int *A, int len)
{
	int i;
	for(i = 1; i <= len; i++)
		cout<<A[i]<<' ';
	cout<<endl;
}
/*************???????????**************************************************/
//????????,???
int Partition(int *A, int p, int r)
{
	int x = A[r], i = p-1, j;
	for(j = p; j < r; j++)
	{
		if(A[j] <= x)
		{
			i++;
			swap(A[i], A[j]);
		}
	}
	swap(A[i+1], A[r]);
	return i+1;
}
int Select(int *A, int p, int r, int i);
//?????start?end??????,?????
//???????,???
int Insert(int *A, int start, int end, int k)
{
	int i, j;
	for(i = 2; i <= end; i++)
	{
		int t = A[i];
		for(j = i; j >= start; j--)
		{
			if(j == start)
				A[j] = t;
			else if(A[j-1] > t)
				A[j] = A[j-1];
			else
			{
				A[j] = t;
				break;
			}
		}
	}
	return A[start+k-1];
}
//???????,???????
int Find(int *A, int p, int r)
{
	int i, j = 0;
	int start, end, len = r - p + 1;
	int *B = new int[len/5+1];
	//?5?????,???start?end,??????????,?????
	for(i = 1; i <= len; i++)
	{
		if(i % 5 == 1)
			start = i+p-1;
		if(i % 5 == 0 || i == len)
		{
			j++;
			end = i+p-1;
			//?????start?end??????,?????,???????,??????????5
			int ret = Insert(A, start, end, (end-start)/2+1);
			//??????????????????
			B[j] = ret;	
		}
	}
	//??????????Select()???????
	int ret = Select(B, 1, j, (j+1)/2);
	//delete []B;
	return ret;
}
#endif
/*
int Find(const ARRAY &array)
{
	int i, j = 0;
	int start, end, len = array.size();
	ARRAY B(array.size()/5+1);
	//?5?????,???start?end,??????????,?????
	for(i = 1; i <= len; i++)
	{
		if(i % 5 == 1)
			start = i-1;
		if(i % 5 == 0 || i == array.size())
		{
			j++;
			end = i-1;
			//?????start?end??????,?????,???????,??????????5
			int ret = Insert(A, (end-start)/2+1);
			//??????????????????
			B[j] = ret;	
		}
	}
	//??????????Select()???????
	int ret = Select(B, (j+1)/2);
	return ret;
}
*/
#if 0
//?f??????
int Partition2(int *A, int p, int r, int f)
{
	int i;
	//??f???????A[r]??
	for(i = p; i < r; i++)
	{
		if(A[i] == f)
		{
			swap(A[i], A[r]);
			break;
		}
	}
	return Partition(A, p, r);
}
//????A[p..r]???i????,i??1????,???p??
int Select(int *A, int p, int r, int i)
{
	//???????????,?????
	if(p == r)
		return A[p];
	//???????,???????
	int f = Find(A, p, r);
	//???????????,?????????A[1..len]???
	//?????????????,???????,A[p..q-1] <= f < A[q+1..r]
	int q = Partition2(A, p, r, f);
	//?????????A[p..r]????
	int k = q - p + 1;
	//??????????
	if(i == k)
		return A[q];
	else if(i < k)
		return Select(A, p, q-1, i);
	else
		//?????????????,????????
		return Select(A, q+1, r, i-k);
		//?????????????????,???????Select(A, q, r, i-k+1)
}
#endif

int select(CArrayFor_9_3_6 & array, int i)
{
	if( i > array.remainDataCount())
		return 0x7fffffff;
	if(array.remainDataCount() == 1)
		return array.data[1];
	return array.data[i];
/*
	//???????????,?????
	if(array.size() == 1)
		return array[0];
	//???????,???????
	int f = Find(A);
	//???????????,?????????A[1..len]???
	//?????????????,???????,A[p..q-1] <= f < A[q+1..r]
	int q = Partition2(A, f);
	//?????????A[p..r]????
	int k = q + 1;
	//??????????
	if(i == k)
		return A[q];
	else if(i < k)
		return Select(A, p, q-1, i);
	else
		//?????????????,????????
		return Select(A, q+1, r, i-k);
		//?????????????????,???????Select(A, q, r, i-k+1)*/
}

ARRAY K_Quantile(CArrayFor_9_3_6 & array, int k)
{
	ARRAY ret;
	if(k == 1)
		return ret;
	int countPerK = array.remainDataCount() / k;
	int midK = (k + 1) / 2;
	int midKth = (midK) * countPerK;
	//cout<<"midKth = "<<midKth<<endl;
	//?????????
	//int x = array.data[midKth];
	int x = select(array, midKth);
//	cout<<"x = "<<x<<endl;
	//int x = Select(A, ((k+1)/2)*t);
	//???????
	//ret.push_back(array.data[array.start]);
	ret.push_back(x);
	//????????????????,??????????????,??SELECT??????????
//	Partition2(A, x);
	//???????????
	if(midK > 1)
	{
		CArrayFor_9_3_6 part1 = array.getPart(array.start, midKth);
		ARRAY ret1 = K_Quantile(part1, midK);
		ret.insert(ret.end(), ret1.begin(), ret1.end());
	}
	if(midK < k - 1)
	{
		CArrayFor_9_3_6 part2 = array.getPart(midKth+1, array.end);
		ARRAY ret2 = K_Quantile(part2, k - midK);
		ret.insert(ret.end(), ret2.begin(), ret2.end());
	}
	return ret;
}

ARRAY solve9_3_6(CArrayFor_9_3_6 & array, int k)
{
	ARRAY ret;
	if(array.remainDataCount() == 0 || 
		k == 0 || 
		array.remainDataCount() % k != 0)
		return ret;
	ret  = K_Quantile(array, k);
	sort(ret.begin(), ret.end());
	return ret;
}
